-- ___       ___  ________   ___  __    _______   ________  ___  ___  ________  ________  ___  ___  ________  _______  _________
--|\  \     |\  \|\   ___  \|\  \|\  \ |\  ___ \ |\   ___ \|\  \|\  \|\   __  \|\   ____\|\  \|\  \|\   ____\|\  ___ \|\___   ___\
--\ \  \    \ \  \ \  \\ \  \ \  \/  /|\ \   __/|\ \  \_|\ \ \  \\\  \ \  \|\  \ \  \___|\ \  \\\  \ \  \___|\ \   __/\|___ \  \_|
-- \ \  \    \ \  \ \  \\ \  \ \   ___  \ \  \_|/_\ \  \ \\ \ \   __  \ \   __  \ \_____  \ \   __  \ \_____  \ \  \_|/__  \ \  \
--  \ \  \____\ \  \ \  \\ \  \ \  \\ \  \ \  \_|\ \ \  \_\\ \ \  \ \  \ \  \ \  \|____|\  \ \  \ \  \|____|\  \ \  \_|\ \  \ \  \
--   \ \_______\ \__\ \__\\ \__\ \__\\ \__\ \_______\ \_______\ \__\ \__\ \__\ \__\____\_\  \ \__\ \__\____\_\  \ \_______\  \ \__\
--    \|_______|\|__|\|__| \|__|\|__| \|__|\|_______|\|_______|\|__|\|__|\|__|\|__|\_________\|__|\|__|\_________\|_______|   \|__|
-- banner online tools
-- https://www.bootschool.net/ascii;bsid=FB5C2059677902AEBA0B2640589E9FE8

local require  = require;
local ngx      = ngx;
local debug    = debug;
local string   = string;
local tonumber = tonumber;
local setmetatable = setmetatable
local pairs    = pairs
local type     = type
local table    = table

local table_concat     = table.concat

local math       = math
local math_floor = math.floor

local uu         = require("modules.commhm.utils");
local log        = require("modules.commhm.log");
local ns_time    = require("modules.commhm.time");


--- CLinkedHashSet 的特性:
--- 1.具有Set的特性,保证元素不重复
--- 2.保证元素有序
--- 3.如果new的时候,capacity_>0,则成为有界队列.队列满时,添加元素,最旧的元素会被丢弃
--- 4.可以当做无重复元素的队列,FIFO.但如果遍历 queue,顺序是与添加顺序相反的
--- 需要注意:
--- A.支持 string 和 number 类型
--- B.添加重复元素时,后来的元素加不进去,而非替换
--- C.由于内部实现中,使用了 queue 和 map 两个table,有一倍的冗余


local _M = { _VERSION = '0.12.1' }
local mt = { __index = _M }


---生成一个新的 CLinkedHashSet
---@param capacity_		number	容量,超出容量则丢弃最旧的元素(0表示无限,默认无限)
---@param module_name_	string	模块名称
---@return table	如果返回nil,则生成失败
function _M.new(capacity_, module_name_)
	module_name_ = module_name_ or "collection_linked_hash_set"
	if type(module_name_) ~= "string" then
		log.error("module_name_ not string!name_="..uu.to_str(module_name_))
		return
	end
	capacity_ = tonumber(capacity_) or 0
	if type(capacity_) ~= "number" then
		log.error(module_name_.." new() capacity_ is not number!!! type(capacity_)="..type(capacity_))
	end

	log.debug( "CLinkedHashSet:new, capacity="..capacity_, "name="..module_name_);
	local ins_ = {
		queue		= {},			---队列(用于保证顺序)
		map			= {},			---字典(用于去重)
		module_name	= module_name_,	---模块名字(用于日志输出)
		capacity	= capacity_,	---限定容量(超出则丢弃)
	};

	local ret_ = setmetatable(ins_, mt);
	return ret_
end

---获取队列长度
---@return number	队列长度
function _M:size()
	return #self.queue
end


---是否包含该元素
---@param node_ string or number
---@return boolean	是否包含
function _M:contains(node_)
	if not node_ then
		log.error(self.module_name.." submit() node_ is nil!!!")
		return false
	elseif type(node_) ~= "number" and type(node_) ~= "string" then
		log.error(self.module_name.." submit() Unsupported node_="..uu.to_str(node_))
		return false
	end

	if self.map[node_] then
		return true
	end
	return false
end


---添加一个新元素,重复元素无法再次添加(如果容量已满,则丢弃最旧的)
---@param node_ string or number
---@return boolean	是否成功
function _M:add(node_)
	if not node_ then
		log.error(self.module_name.." submit() node_ is nil!!!")
		return false
	elseif type(node_) ~= "number" and type(node_) ~= "string" then
		log.error(self.module_name.." submit() Unsupported node_="..uu.to_str(node_))
		return false
	end

	if self:contains(node_) then
		return false
	end

	table.insert(self.queue, 1, node_)
	self.map[node_] = true

	---查看队列是否已满
	if self.capacity > 0 then
		while #self.queue > self.capacity do
			self:pop()
		end
	end

	return true
end

---批量添加元素
---@param list_	table	必须是数组
function _M:add_all(list_)
	if not list_ then
		log.error(self.module_name.." submit_list() list_ is nil!!!")
		return
	elseif type(list_) ~= "table" then
		log.error(self.module_name.." submit_list() list_ not table!!!")
		return
	end

	for i = 1, #list_ do
		local node_ = list_[i]
		self:add(node_)
	end
end


---如果指定元素存在于此 set 中，则将其移除
---@param node_ string or number
---@return boolean	是否包含该元素
function _M:remove(node_)
	if self:contains(node_) then
		for i = 1, #self.queue do
			local tmp_ = self.queue[i]
			if tmp_ == node_ then
				table.remove(self.queue, i)
				self.map[node_] = nil
				return true
			end
		end
	end
	return false
end


---弹出尾部元素
---@return string or number
function _M:pop()
	if #self.queue <= 0 then
		return
	end

	local node_ = self.queue[#self.queue]
	self.queue[#self.queue] = nil
	self.map[node_] = nil
	return node_
end


return _M;
